package leetcode.editor.offer;

// 剑指 Offer 60. n个骰子的点数
// https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/
class NgeTouZiDeDianShuLcof {
    public static void main(String[] args) {
        Solution solution = new NgeTouZiDeDianShuLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
    /*public double[] dicesProbability(int n) {
        // dp[i][j] ，表示投掷完 i 枚骰子后，点数 j 的出现次数。
        int[][] dp = new int[n + 1][6 * n + 1];
        // 初始化，当n=1，只有一个筛子的时候，无论出现几都只有1次
        for (int i = 1; i <= 6; i++) dp[1][i] = i;

        // 遍历塞子
        for (int i = 2; i <= n; i++)
            // 遍历总数，从i开始，每个塞子最小都为1，所以最小每个塞子都是1的情况，此时总数最小就是塞子数量
            // 最大的总数也就是 n * i
            for (int j = i; j <= 6 * i; j++)
                for (int k = 1; k <= 6 && k <= j; k++)
                    dp[i][j] += dp[i - 1][j - k];

        double[] res = new double[5 * n + 1];
        for (int i = n; i <= 6 * n; i++) {
            res[i - n] = ((double) dp[n][i] / Math.pow(6, n));
        }
        return res;
    }*/

        /**
         * 优化为一维数组
         *
         * @param n
         * @return
         */
        //         // https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/solution/nge-tou-zi-de-dian-shu-dong-tai-gui-hua-ji-qi-yo-3/
        public double[] dicesProbability(int n) {
            // dp[i][j] ，表示投掷完 i 枚骰子后，点数 j 的出现次数。
            // 优化：在一条数组上操作
            int[] dp = new int[6 * n + 1];
            // 初始化，当n=1，只有一个筛子的时候，无论出现几都只有1次
            for (int i = 1; i <= 6; i++) dp[i] = 1;

            for (int i = 2; i <= n; i++)
                // 注意这里一定得倒序遍历，和0-1背包倒序的原因一致，防止覆盖
                for (int j = 6 * i; j >= i; j--) {
                    // 一定要加这一步，因为多一个塞子可能次数不一样
                    // 例如：3，三个塞子1次，两个塞子2次
                    dp[j] = 0;
                    for (int k = 1; k <= 6; k++) {
                        // 防止越界，至少都是塞子数
                        if (j - k < i - 1) break;
                        dp[j] += dp[j - k];
                    }
                }

            double[] res = new double[5 * n + 1];
            for (int i = n; i <= 6 * n; i++) {
                res[i - n] = ((double) dp[i] / Math.pow(6, n));
            }
            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
